package com.jxb.seven;

/**
 * 最小路径和
 *
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 *
 * @author jiaobo
 * @date Created in 2025/1/5 14:47
 **/
public class MinimumPathSum_64 {

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        minPathSum2(grid);
    }

    //标准dp实现
    //状态转移表达式：当前位置的最小和 = 当前位置的和 + min(上面位置的和，左边位置的和)
    //dp数组：dp[i][j] = dp[i][j] + min()
    public int minPathSum(int[][] grid) {
        //行数
        int hang = grid.length;
        //列
        int lie = grid[0].length;
        //定义dp数组
        int[][] dp = new int[hang][lie];

        //初始化dp数组
        dp[0][0] = grid[0][0];
        for (int i = 1;i<hang;++i) {
            dp[i][0] = grid[i][0] + grid[i-1][0];
        }
        for (int j = 1;j<lie;++j) {
            dp[0][j] = grid[0][j] + grid[0][j-1];
        }
        //使用状态转移公式，填充dp数组
        for (int i = 1;i<hang;++i) {
            for (int j = 1;j<lie;++j) {
                dp[i][j] = dp[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[hang-1][lie-1];
    }

    /*标准DP+滚动数组实现*/
    //状态转移表达式：当前位置的最小和 = 当前位置的和 + min(前位置的和，当前位置的和)
    //dp数组：dp[j] = grid[i][j] + min(dp[j-1],dp[j])
    //空间复杂度降低为O(lie)
    public static int minPathSum2(int[][] grid) {
        int hang = grid.length;
        int lie = grid[0].length;
        //定义dp数组
        int[] dp = new int[lie];
        //初始化0行，1,4,5
        dp[0] = grid[0][0];
        for (int j = 1;j<lie;j++) {
            int g = grid[0][j];
            int g1 = dp[j-1];
            dp[j] = g + g1;
        }
        //填充dp数组
        for (int i = 1;i<hang;++i) {
            for (int j = 0;j<lie;++j) {
                if (j == 0) {
                    dp[j] = grid[i][j] + dp[j];
                }else {
                    dp[j] = grid[i][j] + Math.min(dp[j],dp[j-1]);
                }
            }
        }
        return dp[lie-1];
    }

}
